Others have proposed template matching techniques for more precisely controlling the size, positioning and number of picture elements ("pixels") that are exposed on a xerographic photoreceptor to render bitmapped images. Heretofore, a number of patents and publications have disclosed resolution enhancement, and hierarchical template-matching, the relevant portions of which may be briefly summarized as follows:
For example, U.S. Pat. No. 4,437,122 to Walsh et al. describes a method of resolution enhancement for a system receiving video display pixel information and providing hard copy output. Enhancement is achieved by storing successive lines of video data in parallel shift registers, applying the output of the shift registers to a decoder, and generating driving signals for a printer head. The decoder "compares tile pixels on the same lines as well as in preceding and succeeding lines that surround each specific input pixel to generate the printer head driving signal according to whether straight or curved line segments are to be formed" (col. 2, lines 6-10). Moreover, enhancement of the central pixel may be determined by "progressively examining an ordered table of matches to find an equivalent image and its related enhancement" (col. 3, line 67-col. 4, line 1).
U.S. Pat. No. 4,847,641 to Tung teaches enhancing the printing of bitmapped images by the piecewise matching of the bitmap with predetermined stored templates of patterns to detect the occurrence of preselected bitmap features. Templates representing compound error elements common to all bitmap images, associated compensation signals for each template, and the rules governing the relationships between the matched templates and the associated compensation signals are compiled into an index matching table implemented in a high speed parallel logic array.
U.S. Pat. No. 5,365,251 to Denber discloses hierarchical pattern matching with variable size templates. A pattern matching template is partitioned into a set of smaller sub-templates, the sub-templates located in the corner units are discarded, and the remaining sub-templates are checked to determine whether the output image in each remaining sub-template is defined as anything other than all-white or all-black. If the output image in each sub-template is so defined, the sub-template is checked with a matching region. The matching region defines an action to be taken on the central pixel and pattern-matching is then performed within the area.
U.S. Pat. No. 5,329,599 to Curry teaches the enhancement of fidelity in reproduced images by hierarchical template matching. The method for enhancing the contour fidelity of images includes isolating a window of pixels in a portion of the image and comparing pixels in the window with a hierarchical set of standard pixel patterns that include correctable pixel positions. Matching patterns are identified, and the central pixel of the window is enhanced when it lies in a correctable position in the highest priority pattern that is matched.
The present invention is adaptable to apply template matching in any system that utilizes multiple patterns in a matching algorithm. Some common applications include enhancement of digital documents, resolution conversion and enhancement of digital documents, image restoration for aesthetic purposes, or human and machine recognition (e.g., OCR, and other feature recognition). Template matching has been effectively employed to overcome some of the sampling errors that are caused by the use of input data that is too coarse to accurately represent the higher spatial frequency content of an image. Note that coarseness refers to sampling in a manner that does not fully represent the information content of the image, which includes coarse spatial sampling (e.g., spots per inch), and coarse quantization (e.g., 1 bit/pixel compared to 8 bits/pixel).
A specific application in which the present invention finds particular use is enhancement of images for electronic printing. In electronic printing, digital character features are often recognized and based upon the recognition and capability of the image writing member, various types of enhanced pixel signals are generated and used to write the final printed or displayed image. Types of enhanced signals include increased quantization range (conversion of binary signal to gray-scale, which is commonly referred to as antialiasing), high addressable signals that control the writing spot over distances smaller than the spot itself, and pulse controlled signals that may activate the writing member (e.g., laser) some preferred length of time that may be shorter than a nominal pixel period.
High-addressability printers operate by scanning one or more intensity modulated scan spots over a high gamma, photosensitive recording medium in accordance with a scan pattern that causes the spot or spots to superimpose displaced multiple discrete exposures on the recording medium. High addressability typically refers to the ability to address the image writing member (e.g., laser) in spatial increments finer than the size of the writing spot, or nominal resolution of the imaging system. High addressability systems have substantially linear edge position responses, so that pixel signals modulated in accordance with the preselected values are used by these systems for spatially positioning the transitions that are contained by the images they render to a sub-pitch (smaller than the writing spot) precision. It is well known that the human visual system is particularly sensitive to jagged edge transitions in image patterns, where this sensitivity is referred to as vernier acuity. The degree of edge placement precision enabled by high addressability aids in suppressing the appearance of jagged image artifacts caused by the coarse sampling.
In accordance with the present invention, there is provided a method of enhancing the contour fidelity of reproduction of an image represented by a plurality of pixels, comprising the steps of:
storing pixel values representing a segment of the image in memory; PA1 isolating a plurality of regions of the pixels of said image segment to form a plurality of windows, each window being of different dimensions while including a common central pixel and a plurality of pixels surrounding said central pixel; PA1 comparing at least two of the regions of pixels within the windows with a set of standard pixel patterns for each of the windows; PA1 identifying matching pixel patterns within each of the windows; and PA1 enhancing the central pixel when the central pixel is located at a correctable position in only one of the windows, and enhancing the central pixel when the central pixel is located at a correctable position in a plurality of the windows wherein the enhancement is accomplished in accordance with an enhancement associated with one of the windows and wherein the enhancement is determined in accordance with a predetermined hierarchy for the windows. PA1 memory for storing pixel values representing a segment of the image; PA1 a plurality of windows for isolating a plurality of regions of the pixels of said image segment, each window being of different dimensions while including a central pixel and a plurality of pixels surrounding said central pixel; PA1 pattern matchers for comparing at least two of the regions of pixels within the windows with a set of standard pixel patterns for each of the windows and signaling the presence of matching pixel patterns within each of the windows; and PA1 said pattern matchers enhancing at least one output pixel when the output pixel is located at a correctable position in only one of the windows, and enhancing the output pixel when the output pixel is located at a correctable position in a plurality of the windows wherein the enhancement is accomplished in accordance with an enhancement associated with one of the windows and wherein the enhancement is determined in accordance with a predetermined hierarchy for the windows.
Note that while the filter windows have been described as having a common central pixel, it is understood by those skilled in the art that the concepts are immediately extendible to windows that contain a plurality of common pixels. Use of multiple common pixels in window mapping is referred to as area mapping. See "AREA MAPPING EMPLOYING REFERENCE CLUSTERS FOR HIGH QUALITY NONINTEGER RESOLUTION CONVERSION WITH ENHANCEMENT" by Loce et al., Application Ser. No. 08/451,376, hereby incorporated by reference, for a description of an area mapping method that may employ the present invention.
In accordance with another aspect of the present invention, there is provided an apparatus for enhancing the contour fidelity of reproduction of an image represented by a plurality of pixels, comprising:
One aspect of the invention is based on the recognition of a problem with conventional and high addressability printing utilized to render enhanced exposure fidelity to a photoreceptor or other recording media. Normally the source of the high fidelity information is a sampled image or a high resolution bitmap. But many raster data sources provide low resolution bitmaps at 300 or 400 bits per inch, which is not enough resolution to eliminate unwanted artifacts induced by the coarseness of the information, such as stairstepping. While resolution enhancement to improve such renderings is known, the present invention is directed to a computationally and costeffective manner to achieve template-matching.
The hierarchical design of the invention has the advantage of simplifying and thereby reducing the cost and complexity of the implementation. Pattern templates are implemented in a set of hierarchical windows, in which the more specific pattern that receives a match has priority over the smaller, more general patterns. Moreover, the patterns are arranged in accordance with the pattern size so as to reduce the storage necessary to implement the very specific patterns.
The technique described above is advantageous because it efficiently reduces the storage requirements of a template-based resolution enhancement system while maintaining the ability to recognize very specific template patterns. As a result of the invention, resolution enhancement using hierarchical template-matching techniques may be accomplished with reduced template pattern storage.